{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Pairs in Two Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计数对"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个长度为 <code>n</code> 的整数数组 <code>nums1</code>&nbsp;和&nbsp;<code>nums2</code> ，找出所有满足 <code>i &lt; j</code> 且 <code>nums1[i] + nums1[j] &gt; nums2[i] + nums2[j]</code>&nbsp;的数对 <code>(i, j)</code> 。</p>\n",
    "\n",
    "<p>返回满足条件数对的<strong> 个数</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [2,1,2,1], nums2 = [1,2,1,2]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>满足条件的数对有 1 个：(0, 2) ，因为 nums1[0] + nums1[2] = 2 + 2 &gt; nums2[0] + nums2[2] = 1 + 1</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [1,10,6,2], nums2 = [1,4,1,5]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>以下数对满足条件：\n",
    "- (0, 1) 因为 nums1[0] + nums1[1] = 1 + 10 &gt; nums2[0] + nums2[1] = 1 + 4\n",
    "- (0, 2) 因为 nums1[0] + nums1[2] = 1 + 6 &gt; nums2[0] + nums2[2] = 1 + 1\n",
    "- (1, 2) 因为 nums1[1] + nums1[2] = 10 + 6 &gt; nums2[1] + nums2[2] = 4 + 1\n",
    "- (1, 3) 因为 nums1[1] + nums1[3] = 10 + 2 &gt; nums2[1] + nums2[3] = 4 + 5\n",
    "- (2, 3) 因为 nums1[2] + nums1[3] = 6 + 2 &gt; nums2[2] + nums2[3] = 1 + 5\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums1.length == nums2.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums1[i], nums2[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-pairs-in-two-arrays](https://leetcode.cn/problems/count-pairs-in-two-arrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-pairs-in-two-arrays](https://leetcode.cn/problems/count-pairs-in-two-arrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,2,1]\\n[1,2,1,2]', '[1,10,6,2]\\n[1,4,1,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        for i in range(n):\n",
    "            nums1[i] = nums1[i] - nums2[i]\n",
    "        nums1.sort()\n",
    "        left = 0\n",
    "        right = n-1\n",
    "        res = 0\n",
    "        while left<right:\n",
    "            target = nums1[left]+nums1[right]\n",
    "            if target>0:\n",
    "                res = res+right - left\n",
    "                right-=1\n",
    "            else:\n",
    "                left+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "int n = nums1.size();\n",
    "        for(int i=0;i<nums1.size();i++){\n",
    "            nums1[i]-=nums2[i];\n",
    "        }\n",
    "        sort(nums1.begin(),nums1.end());\n",
    "        int left=0,right = n-1;\n",
    "        long long res = 0;\n",
    "        while(left<right){\n",
    "            long long target = nums1[left]+nums1[right];\n",
    "            if(target>0) {\n",
    "                res+=right-left;\n",
    "                right--;\n",
    "            } else{\n",
    "                left++;\n",
    "            }\n",
    "        }\n",
    "        return  res;\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        for i in range(n):\n",
    "            nums1[i] = nums1[i] - nums2[i]\n",
    "        nums1.sort()\n",
    "        left = 0\n",
    "        right = n-1\n",
    "        res = 0\n",
    "        while left<right:\n",
    "            target = nums1[left]+nums1[right]\n",
    "            if target>0:\n",
    "                res = res+right - left\n",
    "                right-=1\n",
    "            else:\n",
    "                left+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        for i in range(n):\n",
    "            nums1[i] = nums1[i] - nums2[i]\n",
    "        nums1.sort()\n",
    "        left = 0\n",
    "        right = n-1\n",
    "        res = 0\n",
    "        while left<right:\n",
    "            target = nums1[left]+nums1[right]\n",
    "            if target>0:\n",
    "                res = res+right - left\n",
    "                right-=1\n",
    "            else:\n",
    "                left+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        res = [nums1[i] - nums2[i] for i in range(n)]\n",
    "        res.sort()\n",
    "        l, r = 0, n - 1\n",
    "        ans = 0\n",
    "        while l < r:\n",
    "            while r > l and res[l] + res[r] > 0:\n",
    "                r -= 1\n",
    "            ans += n - r - 1\n",
    "            l += 1\n",
    "            if l >= r:\n",
    "                ans += (n - l - 1) * (n - l) // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        arr = sorted(x - y for x, y in zip(nums1, nums2))\n",
    "        ans = 0\n",
    "        for x in arr:\n",
    "            ans += n - bisect_right(arr, -x) - (x > 0)\n",
    "        return ans // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums1)\n",
    "        sl = SortedList()\n",
    "        for i in range(n):\n",
    "            tmp = nums1[i] - nums2[i]\n",
    "            idx = sl.bisect_left(tmp)\n",
    "            ans += idx \n",
    "            sl.add(-tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        diff = sorted([nums1[i] - nums2[i] for i in range(len(nums1))])\n",
    "        l, r = 0, len(nums1)-1\n",
    "        ans = 0\n",
    "        while l < r:\n",
    "            if diff[r] + diff[l] > 0:\n",
    "                ans += (r-l)\n",
    "                r -= 1\n",
    "            else:\n",
    "                l += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # n=len(nums1)\n",
    "        dif = sorted([nums1[j]-nums2[j] for j in range(len(nums1))])\n",
    "        return sum(len(nums1)-max(j+1,bisect_right(dif,-dif[j])) for j in range(len(nums1)))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
